经典算法题(四)——利用 p, 1-p 随机数发生器知道等概率发生器

已有一个随机数发生器,生成0的概率为p,生成1的概率为1-p,求如何利用这个随机数发生器制作一个生成1~n的概率都是 1/n 的发生器

制作 1 2 发生概率都是 1 / 2 的发生器,连续发生2次,则发生00,11的概率为p*p,(1-p)(1-p),发生10,01的概率都为p(1-p),在发生10时返回1,发生01时返回2,则发生1,2的概率相等

制作 1 2 3 发生概率都是 1 / 3的发生器,连续发生3次,则发生001,010,100的概率都为pp(1-P),或者是110,101,011概率都为p(1-p)(1-p),则用001,010,100分别对应1,2,3返回,即可使得发生1,2,3的概率都为1/3

Jerky Lu wechat
欢迎加入微信公众号